package com.llb666.java.leetcode;

/**
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
 * 而 isConnected[i][j] = 0 表示二者不直接相连。
 * 返回矩阵中 省份 的数量
 * @author 斌~
 * @version 1.0
 * @date 2021/5/19 下午2:44
 */
public class 省份数量 {
    public static void main(String[] args) {
        System.out.println(getProvince(new int[][]{{1,1,0},{1,1,0},{0,0,1}}));   //2
        System.out.println(getProvince(new int[][]{{1,0,0},{0,1,0},{0,0,1}}));   //3
    }

    private static int getProvince(int[][] citysConnected) {
        //城市数量
        int citys = citysConnected.length;
        //访问过的城市标签
        boolean [] visited =new boolean[citys];
        int provinces = 0; //计数器
        for (int i = 0; i < citys; i++) {
            if(!visited[i]){
                dfs(i,citys,visited,citysConnected);
                provinces++;
            }
        }
        return provinces;
    }

    private static void dfs(int i, int citys, boolean[] visited, int[][] citysConnected) {
        for (int j = 0; j < citys; j++) {
            if(citysConnected[i][j]==1 && !visited[j]){
                visited[j]=true;
                dfs(j,citys,visited,citysConnected);
            }
        }
    }
}
